package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author zhangjy
 * @description 二叉树的所有路径
 * @date 2025/4/15 11:19
 */
public class BinaryTreePaths_257 {

    public static void main(String[] args) {
        BinaryTreePaths_257 binaryTreePaths257 = new BinaryTreePaths_257();

        TreeNode node5 = new TreeNode(5, null, null);
        TreeNode node3 = new TreeNode(3, null, null);
        TreeNode node2 = new TreeNode(2, null, node5);
        TreeNode node1 = new TreeNode(1, node2, node3);
        System.out.println(binaryTreePaths257.binaryTreePaths3(node1));
    }

    /**
     * 参考官解-隐藏回溯
     * <p>
     * 思路：
     * 1.错误个解中，用同一个变量path记录每条的路径，并且path随着递归向下传递，每经过一个节点，path就会把其记录到路径中；
     * 所以当一条路径递归结束时，递归需要回到最近一个节点岔路口从而向另一条新路径继续递归，这个给过程中path就需要回溯，移除旧路径经过的节点，然后才能用path继续记录下一条新路径，
     * <p>
     * 2.而这里，虽然也是用path记录每条路径，但是向下传递的是curPath，本层节点压根没记录到path中，相当于这条路径递归结束，又回到本层时，path记录的还是向下递归前的数据（也就是上述回溯后的path），那么也就不需要再次进行回溯，相当于隐藏了回溯过程。
     */
    public List<String> binaryTreePaths6(TreeNode root) {
        List<String> paths = new ArrayList<>();
        if (root == null) return paths;

        getPaths6(root, "", paths);
        return paths;
    }

    public void getPaths6(TreeNode node, String path, List<String> paths) {
        if (node == null) return;

        StringBuilder curPath = new StringBuilder(path);
        if (path.isEmpty()) {
            curPath.append(node.val);
        } else {
            curPath.append("->").append(node.val);
        }

        if (node.left == null && node.right == null) {
            paths.add(curPath.toString());
            return;
        }

        getPaths6(node.left, curPath.toString(), paths);
        getPaths6(node.right, curPath.toString(), paths);

    }

    /**
     * 官解-bfs-迭代
     * <p>
     * 栈、队列、数组都可以实现
     */
    public List<String> binaryTreePaths5(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null)
            return result;
        Stack<Object> stack = new Stack<>();
        // 节点和路径同时入栈
        stack.push(root);
        stack.push(root.val + "");
        while (!stack.isEmpty()) {
            // 节点和路径同时出栈
            String path = (String) stack.pop();
            TreeNode node = (TreeNode) stack.pop();
            // 若找到叶子节点
            if (node.left == null && node.right == null) {
                result.add(path);
            }
            //右子节点不为空
            if (node.right != null) {
                stack.push(node.right);
                stack.push(path + "->" + node.right.val);
            }
            //左子节点不为空
            if (node.left != null) {
                stack.push(node.left);
                stack.push(path + "->" + node.left.val);
            }
        }
        return result;
    }

    /**
     * 官解：dfs-隐藏回溯
     * <p>
     * 思路：
     * 每层path用新的变量记录，这样就不用回溯
     * <p>
     * 复杂度：
     * T(n) = O(n^2)；其中，表示节点数目。在深度优先搜索中每个节点会被访问一次且只会被访问一次，每一次又会对 path 变量进行拷贝构造，时间代价为 O(n)，故时间复杂度为 O(n^2)。
     * S(n) = O(n^2)；
     */
    public List<String> binaryTreePaths4(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        constructPaths4(root, "", paths);
        return paths;
    }

    public void constructPaths4(TreeNode root, String path, List<String> paths) {
        if (root != null) {
            StringBuffer pathSB = new StringBuffer(path);
            pathSB.append(Integer.toString(root.val));
            if (root.left == null && root.right == null) {  // 当前节点是叶子节点
                paths.add(pathSB.toString());  // 把路径加入到答案中
            } else {
                pathSB.append("->");  // 当前节点不是叶子节点，继续递归遍历
                constructPaths4(root.left, pathSB.toString(), paths);
                constructPaths4(root.right, pathSB.toString(), paths);
            }
        }
    }

    /**
     * 个解（参考dmsxl）：dfs-递归
     * 显示回溯
     * <p>
     * 思路：
     * 既然下面两种解法都有问题，主要是因为每层递归把拼接好的路径path传递下去，但是，回溯次数又要受到 节点值的位数和其正负数类型不同的影响；
     * 那么，转变思路，先记录该路径的经过的节点值List<Integer> vals，然后在叶子节点时拼接完整路径，其它时候不拼接；
     * 这样【每层只用回溯一次vals，且每次只回溯一位（即本层节点值）】。
     */
    List<String> ans3 = new ArrayList<>();

    public List<String> binaryTreePaths3(TreeNode root) {
        getLeafPath3(root, new ArrayList<>());
        return ans3;
    }

    public void getLeafPath3(TreeNode node, List<Integer> vals) {
        if (node == null) return;

        // 中
        // 记录本节点值
        vals.add(node.val);
        // 若为叶子，则记录到结果集ans
        if (node.left == null && node.right == null) {
            // 构建本路径完整path，并记录
            StringBuilder path = getPath(vals);
            ans3.add(path.toString());
            // 记录后，要回溯删除本层路径
            vals.remove(vals.size() - 1);
            return;
        }

        // 左
        getLeafPath3(node.left, vals);
        // 右
        getLeafPath3(node.right, vals);

        // 本层递归完，要回溯删除本层路径
        vals.remove(vals.size() - 1);
    }

    public StringBuilder getPath(List<Integer> vals) {
        StringBuilder path = new StringBuilder();

        for (int i = 0; i < vals.size(); i++) {
            // 本路径首次记录，只记录root节点的节点值
            if (path.length() == 0) {
                path.append(vals.get(i));
            } else {
                path.append("->").append(vals.get(i));
            }
        }
        return path;
    }

    /**
     * 个解：递归-先序（错误解法！！！）
     * <p>
     * 思路：
     * 回溯时，很难正确判断，本次回溯要删除几位字符，因为负数、回溯到根节点、正数的处理不同；如-5，要删除的字符就是 '-'、'->'、'-'、'5'，共4位，而正数只用删除'-'、'->'、'5'，共3位。
     * 通过times，根据每层的节点类型，记录要回溯的次数：
     * 1）根节点，回溯0次；
     * 2）普通节点，非负数，'-'、'->'和节点值共回溯3次；
     * 3）普通节点，负数，'-'、'->'、'-'、和节点值共回溯4次，
     * <p>
     * 错误原因：
     * 节点值当作字符串记录到path时，不同位数的节点值占用字符个数不同，正单数-1位，正双数-两位... ... 所以，times不止要根据正负数记录回溯次数，还要结合节点值是几位数来记录回溯次数。
     * 太复杂！！！
     * 转为使用dmsxl解法。
     */
    List<String> ans2 = new ArrayList<>();

    List<Integer> times2 = new ArrayList<>();

    public List<String> binaryTreePaths2(TreeNode root) {
        if (root == null) return ans2;

        getLeafPath2(root, new StringBuilder(), times2);
        return ans2;
    }

    public void getLeafPath2(TreeNode node, StringBuilder path, List<Integer> times) {
        if (node == null) return;

        // 中
        // 记录本节点路径，以及本层节点要回溯的次数。（该路径首次记录，则只记录节点值；否则记录 ->和节点值）
        if (path.length() == 0) {
            times.add(0);
            path.append(node.val);
        } else {
            if (node.val < 0) {
                times.add(4);
            } else {
                times.add(3);
            }
            path.append("->").append(node.val);
        }
        // 若为叶子，则记录到结果集ans
        if (node.left == null && node.right == null) {
            ans2.add(path.toString());
            // 记录后，要回溯删除本层路径
            Integer curTimes = times.get(times.size() - 1);
            times.remove(times.size() - 1);
            for (int i = 0; i < curTimes; i++) {
                path.deleteCharAt(path.length() - 1);
            }
            return;
        }

        // 左、右
        getLeafPath2(node.left, path, times);
        getLeafPath2(node.right, path, times);
        // 本层递归完，回溯删除本层路径
        Integer curTimes = times.get(times.size());
        times.remove(times.size() - 1);
        for (int i = 0; i < curTimes; i++) {
            path.deleteCharAt(path.length() - 1);
        }
    }

    /**
     * 个解：递归-先序（错误解法！！！）
     * <p>
     * 思路：
     * <p>
     * 前序，因为要记录路径，所以得先访问本层节点，才能让路径中父节点指向孩子节点
     * 该题中，虽然统计的是root——>叶子节点的路径，但是由示例可知，只有一个root节点，也要记录其路径（有些题中，统计root到叶子节点，那只有一个root节点就不会加入统计）。
     * <p>
     * 错误原因：
     * <p>
     * 回溯时，很难正确判断，本次回溯要删除几位字符，因为负数、回溯到根节点、正数的处理不同；如-5，要删除的字符就是 '-'、'->'、'-'、'5'，共4位，而正数只用删除'-'、'->'、'5'，共3位。
     */
    List<String> ans = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        if (root == null) return ans;

        getLeafPath(root, new StringBuilder());
        return ans;
    }

    public void getLeafPath(TreeNode node, StringBuilder path) {
        if (node == null) return;

        // 中
        // 记录本节点路径。该路径首次记录，则只记录节点值；否则记录 ->和节点值
        if (path.length() == 0) {
            path.append(node.val);
        } else {
            path.append("->").append(node.val);
        }
        // 若为叶子，则记录到结果集ans
        if (node.left == null && node.right == null) {
            ans.add(path.toString());
            // 记录后，要回溯删除本层路径：'-'、'>' 和节点值
            if (path.length() > 1) {
                path.deleteCharAt(path.length() - 1);
                path.deleteCharAt(path.length() - 1);
                path.deleteCharAt(path.length() - 1);
            }
            return;
        }

        // 左、右
        getLeafPath(node.left, path);
        getLeafPath(node.right, path);
        // 本层递归完，回溯删除本层路径：'-'、'>' 和节点值
        if (path.length() > 1) {
            path.deleteCharAt(path.length() - 1);
            path.deleteCharAt(path.length() - 1);
            path.deleteCharAt(path.length() - 1);
        }
    }

}
